class Solution:
    def maxProfit(self, prices) -> int:
        if len(prices) <= 1:
            return 0
        dpLeft = [0 for _ in range(len(prices))]
        dpRight = [0 for _ in range(len(prices))]
        min_price = prices[0]
        for i in range(1, len(prices)):
            dpLeft[i] = max(prices[i] - min_price, dpLeft[i - 1])
            if prices[i] < min_price:
                min_price = prices[i]
        max_price = prices[-1]
        for i in range(len(prices) - 3, 0, -1):
            dpRight[i] = max(max_price - prices[i + 1], dpRight[i - 1])
            if prices[i + 1] > max_price:
                max_price = prices[i + 1]

        return max([dpLeft[i] + dpRight[i] for i in range(len(prices))])


if __name__ == '__main__':
    so = Solution()
    t = [2, 1, 4, 5, 2, 9, 7]
    r = so.maxProfit(t)
    print(r)
